#include<assert.h>
#include<iostream>

namespace MyL
{
  template<class T>
  struct ListNode
  {
    ListNode(const T& val = T())
      :_date(val),
      _next(nullptr),
      _front(nullptr)
    {}
    T _date;
    ListNode<T>* _next;
    ListNode<T>* _front;
  };

  template<class T>
  struct _list_iterator
  {
    typedef ListNode<T> Node;
    public:
    _list_iterator(Node* pos)
      :_it(pos)
    {}
    ~_list_iterator()
    {}
    _list_iterator& operator++()
    {
      _it = _it->_next;
      return *this;
    }
    _list_iterator operator++(int)
    {
      Node* tmp = _it;
      _it = _it->_next;
      return tmp;
    }
    _list_iterator operator--()
    {
      _it = _it->_front;
      return *this;
    }
    _list_iterator& operator--(int)
    {
      Node* tmp  = _it;
      _it = _it->_front;
      return tmp;
    }
    bool operator!=(const _list_iterator& pos)
    {
      return (_it != pos._it);
    }
    T& operator*()
    {
      return _it->_date;
    }
    T* operator->()
    {
      return &(_it->_date);
    }
    Node* _it;
  };

  template<class T>
  class list
  {
    typedef ListNode<T> Node;
  public:
    typedef _list_iterator<T> iterator;
    list()
      :_head(new Node)
    {
      _head->_next = _head;
      _head->_front = _head;
    }
    iterator begin()
    {
      return iterator(_head->_next);
    }
    iterator end()
    {
      return iterator(_head);
    }
    void push_back(const T& date)
    {
      Node* tail = _head->_front;
			Node* newnode = new Node(date);

			// _head       tail  newnode
			tail->_next = newnode;
			newnode->_front = tail;
			newnode->_next = _head;
			_head->_front = newnode;
      //insert(end(),date);
    }
    iterator insert(iterator pos,const T& date)
    {
      Node* newnode = new Node(date);
      Node* cur = pos._it;
      Node* fornt = cur->_front;
      //front new cur 
      fornt->_next = newnode;
      newnode->_front = fornt;
      newnode->_next = cur;
      cur->_front = newnode;
      return iterator(newnode);
    }
  private:
    Node* _head;
  };
}
